/*
 * @lc app=leetcode.cn id=152 lang=golang
 *
 * [152] 乘积最大子数组
 */

// 2.
// @lc code=start
func maxProduct(nums []int) int {
	minV, maxV, ans := nums[0], nums[0], nums[0]

	for i := 1; i < len(nums); i++ {
		mxV := maxV
		maxV = max(maxV*nums[i], max(nums[i], minV*nums[i]))
		minV = min(minV*nums[i], min(nums[i], mxV*nums[i]))

		ans = max(ans, maxV)
	}
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// @lc code=end

// 1. 动态规划
// @lc code=start
func maxProduct(nums []int) int {
	minF := make([]int, len(nums))
	maxF := make([]int, len(nums))
	copy(minF, nums)
	copy(maxF, nums)

	for i := 1; i < len(nums); i++ {
		maxF[i] = max(maxF[i-1]*nums[i], max(nums[i], minF[i-1]*nums[i]))
		minF[i] = min(minF[i-1]*nums[i], min(nums[i], maxF[i-1]*nums[i]))
	}
	ans := maxF[0]
	for i := 1; i < len(nums); i++ {
		ans = max(ans, maxF[i])
	}
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// @lc code=end

 